//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 105 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 1058 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

//Java：最小覆盖子串
public class P76MinimumWindowSubstring{
    public static void main(String[] args) {
        Solution solution = new P76MinimumWindowSubstring().new Solution();
        // TO TEST
        String minWindow = solution.minWindow("ADOBECODEBANC", "ABC");
        System.out.println(minWindow);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> needMap = new HashMap();
        int count = t.length();
        char[] chars = t.toCharArray();
        for (char aChar : chars) {
            needMap.put(aChar, 1);
        }
        char[] sArray = s.toCharArray();
        int left = 0;
        int right = 0;
        String minWindow= "";
        while (right < s.length()){
            //移动右窗口
            char rVal = sArray[right];
            if(needMap.containsKey(rVal) && Objects.equals(1, needMap.get(rVal))){
                needMap.put(rVal, 0);
                count = count - 1;
            }
            //满足条件
            if(count == 0){
                minWindow = s.substring(left, right+1);
                //移动left
                while(left < right){
                    if(needMap.containsKey(rVal) && Objects.equals(0, needMap.get(rVal))){
                        count = count + 1;
                        needMap.put(rVal, 1);
                    }
                    if(count > 0){
                        right = right + 1;
                        break;
                    }
                    left = left + 1;
                }
            }
            right = right + 1;
        }
        return minWindow;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
